// coding: utf-8

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include "slinked_list.hh"

typedef SLinkedListNode<int32_t> ListNode;

ListNode* list_create()
{
    return new ListNode(0);
}

void list_destroy(ListNode* list)
{
    if (!list) return;
    auto node = list;
    while (node)
    {
        auto next = node->next;
        delete node;
        node = next;
    }
}

void list_insert(ListNode* list, int32_t data)
{
    if (!list)
        return;
    auto tail = list->next;
    while (tail && tail->next)
    {
        tail = tail->next;
    }
    auto node = new ListNode(data);
    if (tail == nullptr)
        list->next = node;
    else
        tail->next = node;
}

void list_print(ListNode* list)
{
    std::cout << "print_list:";
    if (!list)
    {
        std::cout << std::endl;
        return;
    }
    auto node = list->next;
    while (node)
    {
        std::cout << node->data << ",";
        node = node->next;
    }
    std::cout << std::endl;
}

// @brief 删除指定值
ListNode* list_remove(ListNode* list, int32_t val)
{
    auto head = list->next;
    auto pre_node = list;
    auto cur_node = head;
    auto next_node = head->next;
    while (cur_node)
    {
        if (cur_node->data == val)
        {
            pre_node->next = next_node;
            break;
        }
        pre_node = cur_node;
        cur_node = next_node;
        next_node = next_node ? next_node->next : nullptr;
    }
    return list;
}

// @brief 翻转
void list_reverse(ListNode* list)
{
    auto vhead = list;
    auto head = vhead->next;
    // 0节点或者1节点，直接返回
    if (!head || !head->next)
        return;
    ListNode* prev = nullptr;
    ListNode* cur = head;
    ListNode* next = head->next;
    while (cur)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = next ? next->next : nullptr;
    }
    vhead->next = prev;
}

// @brief 递归解法
// 1.链表长度<=1直接放回
// 2.链表长度==2，即node->next->next为空的时候，直接反转前后两个节点，并返回新的head
// 3.链表长度>=2，将node->next进行递归，获取到的结果为head，将node添加到head的tail位置
ListNode* list_reverse2_none_vhead(ListNode* node)
{
    if (!node->next)
        return node;
    // 最后两个节点
    if (!node->next->next)
    {
        auto head = node->next;
        head->next = node;
        node->next = nullptr;
        return head;
    }
    auto new_head = list_reverse2_none_vhead(node->next);
    auto new_tail = new_head;
    while (new_tail->next)
    {
        new_tail = new_tail->next;
    }
    new_tail->next = node;
    node->next = nullptr;
    return new_head;
}

// @brief 反转链表递归解法
ListNode* list_reverse2(ListNode* list)
{
    auto head = list->next;
    auto new_head = list_reverse2_none_vhead(head);
    list->next = new_head;
    return list;
}



// @brief 合并并且保持顺序
ListNode* list_join(ListNode* left, ListNode* right)
{
    auto left_node = left->next;
    auto right_node = right->next;
    ListNode* new_list = list_create();
    ListNode* cur_node = nullptr;
    while (left_node || right_node)
    {
        ListNode* new_node = nullptr;
        if (!left_node && right_node)
        {
            new_node = right_node;
            right_node = right_node->next;
        }
        else if (left_node && !right_node)
        {
            new_node = left_node;
            left_node = left_node->next;
        }
        else
        {
            if (left_node->data <= right_node->data)
            {
                new_node = left_node;
                left_node = left_node->next;
            }
            else
            {
                new_node = right_node;
                right_node = right_node->next;
            }
        }
        new_node->next = nullptr;
        if (!new_list->next)
        {
            new_list->next = new_node;
            cur_node = new_node;
        }
        else
        {
            cur_node->next = new_node;
            cur_node = new_node;
        }
    }
    return new_list;
}


int main()
{
    std::vector<int32_t> vec;
    const int32_t data_len = 6;
    for (int32_t n = 0; n < data_len; n++)
    {
        vec.emplace_back(n);
    }
    //std::shuffle(vec.begin(), vec.end(), std::default_random_engine());

    auto list = list_create();
    for (auto iter = vec.begin(); iter != vec.end(); ++iter)
    {
        list_insert(list, *iter);
    }

    auto list1 = list_create();
    for (auto iter = vec.begin(); iter != vec.end(); ++iter)
    {
        list_insert(list1, *iter);
    }

    list_print(list);
    std::cout << "reverse" << std::endl;
    list_reverse(list);
    list_print(list);
    std::cout << "remove 2" << std::endl;
    list_remove(list, 2);
    list_print(list);
    std::cout << "remove 0" << std::endl;
    list_remove(list, 0);
    list_print(list);
    std::cout << "remove 5" << std::endl;
    list_remove(list, 5);
    list_print(list);
    std::cout << "reverse" << std::endl;
    list_reverse(list);
    list_print(list);
    std::cout << "reverse2" << std::endl;
    list_reverse2(list);
    list_print(list);
    std::cout << "join" << std::endl;
    auto nlist = list_join(list1, list);
    list_print(nlist);
    std::cout << "reverse2" << std::endl;
    list_reverse2(nlist);
    list_print(nlist);
    //list_destroy(list);

    return 0;
}
